import java.util.Random;

public class Solution2 {
    public int findKthLargest(int[] nums, int k) {
        return selectK(nums, nums.length - k, new Random());
    }

    private int selectK(int[] arr, int k, Random random) {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int p = partition(arr, l, r, random);
            if (p == k) return arr[p];
            if (p < k) l = p + 1;
            else r = p - 1;
        }
        return -1;
    }

    private int partition(int[] arr, int l, int r, Random random) {
        //得到[l,r]之间的随机索引
        int p = random.nextInt(r - l + 1) + l;
        swap(arr, p, l);

        //arr[l+1,i-1]<=v    ;   arr[j++,r]>=v
        int j = r, i = l + 1;
        while (true) {
            while (i <= j && arr[i] < arr[l]) i++;
            while (i <= j && arr[j] > arr[l]) j--;
            if (i >= j) break;
            swap(arr, i, j);
            i++;
            j--;
        }
        swap(arr, l, j);
        return j;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
